The present invention generally relates to computer-based digital image processing. The invention relates more specifically to methods and electronic circuits useful in interpolating edge portions of a digital image.
Color display devices are used by many computers and by computer-related devices such as digital cameras. These displays generally comprise a two-dimensional matrix of display elements or pixels. Each pixel comprises a Red (xe2x80x9cRxe2x80x9d), Green (xe2x80x9cGxe2x80x9d), and Blue (xe2x80x9cBxe2x80x9d) cell. Each pixel of the display device is represented by a corresponding memory cell that may store a numeric value. The memory cell values usually are 8, 10, or 12 bits in size, and may be stored in any other convenient size. A computer program may cause a particular pixel to glow in any visible color, or to appear black or white, by setting the numeric values of its red, green, and blue cells to an appropriate value.
In many products and applications, some of the pixel information is computer-generated or xe2x80x9cinterpolatedxe2x80x9d by a computer processor or CPU based on other information. Within the general field of computer graphics displays, there is an acute need to improve the way that displays generate or interpolate missing color information. In products that use display devices that are driven by a sensor, there is a particular need to improve the methods and mechanisms that are used to generate interpolated color information.
The following description will focus on particular problems encountered with digital cameras that use CCD sensors to receive light and form a digital picture for display by a color LCD display of the camera. However, the problems described herein occur in many other contexts, and the solutions described herein are applicable to such contexts. For example, the problems and solutions described herein are applicable to all color area sensors that use a two-dimensional array of sensing elements.
Generally, when a digital camera CPU receives image information from the camera sensor, each pixel provided by the sensor represents only one optical color, usually Red, Blue, or Green. The pixels arrive at the CPU in a pattern, which corresponds to the physical placement of sensing elements in the sensor. In one pattern, a first line of the sensor has alternating Red and Green pixels, and the next line has alternating Green and Blue pixels. The pattern continues for the entire CCD sensor, which has a checkerboard or mosaic pattern.
FIG. 5A is a block diagram of a 7-by-7 portion 500 of sensor elements 502, 504, 506 illustrating one pattern that is used by some CCD sensors. A first line 510 of portion 500 comprises a first Red pixel 502a, a first Green pixel 504a, a second Red pixel 502b, a second Green pixel 504b, and so on in an alternating pattern. Second line 512 or portion 500 has a first Green pixel 504c, a first Blue pixel 506a, a second Green pixel 504d, a second Blue pixel 506b, and so forth. This two-line pattern is repeated across the entire surface of the sensor. When the sensor delivers pixel information to a CPU or other element, the information arrives in the same pattern.
Each pixel value may be an 8-bit quantity, 10-bit quantity, 12-bit quantity, or a numeric quantity of some other size. For convenience, in FIG. 5 each pixel is labeled with a numeral from 11 to 77 that identifies its relative position in the 7-by-7 portion 500.
In the foregoing pattern, there are twice as many Green pixels as there are Blue pixels or Red pixels. This is done because the human eye has been found to perceive Green as the most important color in an image, and also because the semiconductor materials that are used to form the sensors are less sensitive to light of Green wavelengths.
The pixel information received using this checkerboard pattern, however, cannot be directly displayed on a graphic display device. An image may be produced only by adding further pixel information to the received pattern of pixel data. Each element of the display comprises the combination of a Red, Green, and Blue pixel and corresponding pixel values, however, each element of the sensor represents only one of the three colors. Thus, two additional complementary color values must be generated and stored in association with the single color value received from the sensor.
For example, in the first line of the portion 500 of FIG. 5, for the first Red pixel 502a, Green and Blue color values must be created and stored. For the next pixel, which is Green pixel 504a, a Red value and a Blue value must be created and stored. This process is called xe2x80x9ccolor interpolationxe2x80x9d and must be rapidly carried out for every pixel value that is received from the sensor. An image may be displayed only after the interpolation step is complete.
Several past approaches are known for carrying out color interpolation. For example, bilinear interpolation involves an averaging approach. At each Blue pixel, to interpolate the Green value, the surrounding four (4) Green values actually received from the sensor are obtained, and their arithmetic mean is computed. The mean value becomes the interpolated Green value. This approach is simple, but relatively inaccurate in terms of color fidelity and image appearance.
A more accurate prior approach is bicubic color interpolation. Bicubic interpolation is similar to bilinear interpolation, but involves using more neighboring pixels and applying a computation that is more complex than averaging.
In one approach, the computation considers a 7-by-7 matrix of pixels, in which the target pixel for which interpolation is carried out lies at the center of the matrix, and the computation considers three (3) neighbor pixels in each linear direction. For example, the matrix of FIG. 5 may be used. In this example, Blue pixel 41 is the center pixel for which interpolation is carried out and all other pixels illustrated in FIG. 5 are neighbors. In this approach, a corresponding matrix of coefficient values is defined and stored. Each coefficient has a floating-point value between xe2x80x9c0xe2x80x9d and xe2x80x9c1xe2x80x9d. Each coefficient value is defined by a nonlinear curve that reflects the relative contribution of each neighbor pixel to the complementary color values of the center pixel. Each coefficient value of all neighbor pixels of a particular color is multiplied by the value of the center pixel, then all the products are summed, and then the arithmetic mean of the products is taken. The result is the pixel value for that particular color.
Other past approaches are described in J. A. Parker et al., xe2x80x9cComparison of Interpolating Methods for Image Resampling,xe2x80x9d MI-2 IEEE Transactions on Medical Imaging 31 (March 1983).
Another method for interpolating missing color information is described in copending U.S. application Ser. No. 09/295,727, filed Apr. 20, 1999 by Sobel et al. (xe2x80x9cSobelxe2x80x9d). In general, Sobel discloses an improved approach for carrying out color interpolation computations for digital images within the computation horsepower available in a digital camera. As described in Sobel, a typical CCD camera sensor comprises an array of CCD sensors arranged in rows and columns. Between each column of CCDs there is a vertical shift register. At the bottom of all the columns is a horizontal shift register. When an image is formed by opening the shutter of the camera, each sensor in the array, which represents a pixel, is exposed for a length of time that is determined by a sensor controller. Then, information produced by all the sensors is transferred to the vertical shift registers. The information is then transferred, one pixel value at a time, to the horizontal shift register. The first pixel that is transferred corresponds to the upper left part of picture.
Thus, serial data is delivered from the sensor to a CPU, or to another hardware device such as photo processor 208 shown in FIG. 2. The CPU or other hardware device xe2x80x9cseesxe2x80x9d a line of pixel data comprising a Red value, Green value, Red value, Green value, and so forth. The next line of pixel data comprises alternating Green and Blue values. Generally, the lines are 1024 to 3000 pixels long, and the pixel data is delivered by the sensor at about 20 MHz.
Using the techniques of Sobel, a register array automatically holds data values for pixels in a predetermined vicinity of the target pixel, e.g., in a 7xc3x977 matrix array, while the values in other pixels of the image are either in the shift registers or non-volatile memory of the device. This arrangement saves the time of performing a random access retrieval from memory or non-volatile storage. This may be a substantial savings for a digital camera with limited computational resources. Before the CPU or other device may carry out interpolation on the pixel data, the CPU corrects for any errors in each pixel value. For example, the CPU may carry out photo-response non-uniformity (PRNU) correction. PRNU correction generally involves multiplying pixel data that corresponds to a particular color by a correction factor or co-efficient that corrects for non-uniformity of the color filters of the CCD for that particular color. For example, it is known that certain semiconductor materials, from which the sensors are made, are more sensitive to red light than to blue light. PRNU correction adjusts for this variance in sensitivity.
After PRNU correction, a stream of corrected pixel data arrives at the CPU or other hardware device. The CPU may transfer the values to a memory, such as a high-performance SDRAM. The CPU may then begin carrying out interpolation of the missing color information. For example, the CPU may apply bicubic color interpolation using 7-by-7 blocks of memory.
Unfortunately, these interpolation approaches generally produce acceptable interpolated results only when neighboring pixels of the value being interpolated are relatively consistent in color compared to the missing color information. This is generally true in most regions of an original image that have relatively gradual changes in color from pixel to pixel. However, images that include sharp edges present a problem.
In a portion of an image that represents the edge of an object, color changes may be extreme from one pixel to the next. For example, consider an original image comprising a dark object viewed in front of a light background; sharp color changes occur at the edge of an object. Further consider an image of a light colored human face against a dark background (or the converse). The cheek portion of the face in the image may have relatively consistent coloration, but at the edge of the cheek there may be a transition (xe2x80x9cfall-offxe2x80x9d) from light to dark. Some changes may occur within one pixel worth of information, i.e., it is possible that an image will transition from a black color value (one extreme) to a white color value (another extreme), and vice versa. In this context, an xe2x80x9cedgexe2x80x9d of an image refers to any region of sharp color contrast in an image, not necessarily the physical edge or outermost pixels of the image. When determining the appropriate color values of an edge of an image, current interpolation approaches may use some data from one side of the edge and some data from the other side of the edge to derive the missing color information. If an interpolation approach is used for an image with an abrupt edge portion or transition region, at some point the interpolator must consider and resolve pixel values at the edge portion or for the transition region. If an abrupt color change occurs within fewer pixels than the interpolation process considers within one (1) iteration of interpolation, for example, in fewer than seven (7) pixels for an interpolation process that uses a 7xc3x977 matrix, then the interpolation process will produce colors that do not really reflect the true color of the region of change.
Accordingly, severe color error may result, because the interpolated color is not a color that was part of the original image. Also because the values on each side of the edge may vary significantly, fuzziness, shimmering, or other undesirable effects may occur in an interpolated edge portion of an image.
Such problems become acute when bicubic interpolation approaches are used. Use of a 7xc3x977 matrix for evaluation means that the values used in the interpolation will extend out three (3) values on each side of the edge. Accordingly, using three (3) values from the wrong side of the edge means that the final interpolated value is potentially more heavily weighted with incorrect color values.
Thus, there is a need for an improved method for interpolating color information in a digital image at a location in an image where abrupt color changes occur.
In the field of digital cameras, there is a particular need for an improved method and apparatus for interpolating color information at edge portions or color transition regions of digital images that are formed by the cameras using the limited computational resources of the digital camera.
The foregoing needs, and other needs and objects that will become apparent from the following description, are achieved by the present invention, which comprises, in one aspect, a method of interpolating image values that selectively elects to carry out a bicubic interpolation of an image region or a directed linear interpolation of a subset of the image region, according to whether the image region contains an edge. In one embodiment, an edge detection test is performed for each new pixel that is received using data in the image region in the vicinity of the pixel. When edge detection is positive, then a directed linear interpolation process is carried out for the corresponding pixel using data in a subset of the image region, thereby minimizing color error. When edge detection is negative, bicubic interpolation is carried out.
In a preferred embodiment, before a color value is interpolated, a 7xc3x977 matrix of pixels is considered for edge detection. If an edge is identified within the matrix, or if a region is otherwise determined to be an edge, bicubic interpolation is not performed. Rather, a linear interpolation approach is applied to a 3xc3x973 matrix subset of the 7xc3x977 matrix of pixels usually used for interpolation, and the pixels in such a subset matrix are selected from only the correct side of the edge.
In one aspect, a method and apparatus for interpolating color image information are provided. One or more image data values for a portion of a digital image in a vicinity of a target pixel are received and stored in a local array. A processor determines whether there is an edge in the vicinity of the target pixel based on the data values in the local array. If there is not an edge in the vicinity of the target pixel, then long scale interpolation is performed on the image data values in the local array, in order to result in interpolating color information that is missing from the image. If there is an edge in the vicinity of the target pixel, then short scale interpolation is performed using image data values in a subset of the local array in a closer vicinity of the target pixel. As a result, accurate color rendering of a digital image is achieved, even in the presence of an edge portion that exhibits great contrast between regions of the image.